"""A Scheme interpreter and its read-eval-print loop."""

import sys
import os

from scheme_builtins import *
from scheme_reader import *
from ucb import main, trace

class Value:
    """Base of all kind of value"""
    kind = 'nil'

# def check_define_permission(symbol, env): # may be used in future
#     """check if the env could define the symbol """
#     # if env.check_resolved(symbol) and symbol in {}:
#     #     # raise SchemeError(f"define '{symbol}' in env is illegal")


def make_tail_expr(cur_env, expr):
    return Pair(None, Pair(cur_env, Pair(expr, nil)))

def scheme_define(args, env):
    """create a new value in env"""
    """there are still risk of replacing builtin produceres or special forms"""
    left = args.first
    expr = args.rest

    if isinstance(left, str): # define a single symbol
        env.define(left, scheme_eval(expr.first, env))
        if expr.rest != nil:
            raise SchemeError("too many operands in form define")
        ret = left
    elif isinstance(left, Pair): # define a user-defined Procedure
        env.define(left.first, scheme_eval(Pair('lambda', Pair(left.rest, expr)), env))
        ret = left.first
    else:
        raise SchemeError("define: unreconized form:", left)
    
    return ret

def scheme_define_macro(args, env):
    left = args.first
    expr = args.rest
    if not isinstance(left, Pair) or not isinstance(left.first, str):
        raise SchemeError("define-macro: invalid left side")
    forms = left.rest
    env.define(left.first, SchemeMacro(forms, expr))
    ret = left.first

    return ret
def scheme_begin(args, env):
    """last element of expr must be env"""
    ret = nil
    while args != nil:
        ret = scheme_eval(args.first, env)
        args = args.rest

    return ret

def scheme_lambda(args, env):
    forms = args.first
    body = args.rest
    form_args = forms

    # check type error
    while form_args != nil:
        if not isinstance(form_args, Pair):
            raise SchemeError("argument 0 of LambdaProcedure has wrong type (symbol)")

        if not isinstance(form_args.first, str): # judge symbol
            raise SchemeError(f"formal args should be a symbol: {form_args.first}")
        form_args = form_args.rest

    return LambdaProcedure(forms, body, env)

def mu_lambda(args, env):
    forms = args.first
    body = args.rest
    form_args = forms

    # check type error
    while form_args != nil:
        if not isinstance(form_args, Pair):
            raise SchemeError("argument 0 of LambdaProcedure has wrong type (symbol)")

        if not isinstance(form_args.first, str): # judge symbol
            raise SchemeError(f"formal args should be a symbol: {form_args.first}")
        form_args = form_args.rest

    return MuProcedure(forms, body)

def scheme_quote(expr):
    return expr.first

def scheme_test(value):
    if value is False:
        return False
    return False if value is False else True

def scheme_and(args, env):
    ret = True
    while args != nil:
        ret = scheme_eval(args.first, env)
        if not scheme_test(ret):
            return False
        args = args.rest
    
    return ret

def scheme_or(args, env):
    ret = False
    while args != nil:
        ret = scheme_eval(args.first, env)
        if scheme_test(ret):
            return ret
        args = args.rest

    return ret

def scheme_not(args, env):
    ret = False
    if args != nil:
        ret = scheme_eval(args.first, env)
        if args.rest != nil:
            raise SchemeError('incorrect number of arguments: #[not]')
    return not scheme_test(ret)

def scheme_if(args, env):
    predicate = args.first
    args = args.rest
    consequent = args.first
    args = args.rest
    alternative = args
    if alternative != nil:
        if alternative.rest != nil:
            raise SchemeError('too many operands in form #[if]')
        alternative = alternative.first

    if scheme_test(scheme_eval(predicate, env)):
        return make_tail_expr(env, consequent)# scheme_eval(consequent, env)
    elif alternative != nil:
        return make_tail_expr(env, alternative)# scheme_eval(alternative, env)
    return None

def scheme_cond(args, env):
    p_clause = args

    while p_clause != nil:
      clause = p_clause.first
      test = clause.first
      ret = scheme_eval(test, env)
      test = scheme_test(ret)
      if test:
          p_expr = clause.rest
          while p_expr != nil:
              ret = scheme_eval(p_expr.first, env)
              p_expr = p_expr.rest
          return ret
      p_clause = p_clause.rest
    
    return None

def scheme_let(args, env):
    p_bindings = args.first
    p_exprs = args.rest
    frame = Frame(env)

    ret = None
    while p_bindings != nil:
        tmp_frame = Frame(env)
        # print("DEBUG: let", Pair('define', p_bindings.first))
        ret = scheme_eval(Pair('define', p_bindings.first), tmp_frame)
        frame.bindings.update(tmp_frame.bindings)
        p_bindings = p_bindings.rest

    while p_exprs != nil:
        ret = scheme_eval(p_exprs.first, frame)
        p_exprs = p_exprs.rest

    return ret
        
##############
# Eval/Apply #
##############

def scheme_process_parms(proc, args, env):#, forms, name="unknown"):
    """
        proc: a Procedure
        args: a Pair, which should not be change
        env: 
        return a args
    """
    ret_args = args
    name = proc.name
    if isinstance(proc, LambdaProcedure): # only LambdaProcedure need verify params nums
        p_forms = proc.formals
        p_args = args
        while p_args != nil and p_forms != nil: # verify nums of params
            p_args = p_args.rest
            p_forms = p_forms.rest
        if p_args != nil or p_forms != nil:
            raise SchemeError(f"scheme_verify_parms: Incorrect number of arguments \
                to function call [{name}]")
    

    if not isinstance(proc, SpecialForm): # special Form don't need eval
        head_args = Pair(0, nil)
        p_head_args = head_args
        p_args = args
        while p_args != nil: # eval each args
            p_head_args.rest = Pair(scheme_eval(p_args.first, env), nil)
            p_head_args = p_head_args.rest
            p_args = p_args.rest
        
        ret_args = head_args.rest
    return ret_args


def scheme_eval(expr, env, _=None): # Optional third argument is ignored
    """Evaluate Scheme expression EXPR in environment ENV.

    >>> expr = read_line('(+ 2 2)')
    >>> expr
    Pair('+', Pair(2, Pair(2, nil)))
    >>> scheme_eval(expr, create_global_frame())
    4
    """
    # PROBLEM 2
    if type(expr) in (bool, int, float) or expr is nil:
        return expr
    elif type(expr) is Pair: # Call Expresion
        op = expr.first
        op = scheme_eval(op, env) # eval a function
        if not isinstance(op, Procedure):
            raise SchemeError(f"{expr.first} is not callable: {op}")
        args = scheme_process_parms(op, expr.rest, env)

        ret = scheme_apply(op, args, env)
        while isinstance(ret, Pair) and ret.first is None: # tail recuresion
            ret = scheme_eval(ret.rest.rest.first, ret.rest.first)
        return ret
    elif type(expr) is str: # Symbol
        return env.resolve(expr)
    elif expr is None: # empty expression
        return None
    else:
        raise SchemeError(f"unreconized expression {repr(expr)}")


def scheme_apply(procedure, args, env):
    """Apply Scheme PROCEDURE to argument values ARGS (a Scheme list) in
    environment ENV."""
    # PROBLEM 2
    ret = procedure.apply(args, env)

    return ret

################
# Environments #
################

class Frame:
    """An environment frame binds Scheme symbols to Scheme values."""

    def __init__(self, parent):
        """An empty frame with parent frame PARENT (which may be None)."""
        "Your Code Here"
        # Note: you should define instance variables self.parent and self.bindings
        self.parent = parent
        self.bindings = {}

    def __repr__(self):
        if self.parent is None:
            return '<Global Frame>'
        s = sorted(['{0}: {1}'.format(k, v) for k, v in self.bindings.items()])
        return '<{{{0}}} -> {1}>'.format(', '.join(s), repr(self.parent))

    def define(self, symbol, value):
        """Define Scheme SYMBOL to have VALUE."""
        self.bindings[symbol] = value

    # BEGIN PROBLEM 2/3
    "*** YOUR CODE HERE ***"
    def resolve(self, symbol):
        if symbol not in self.bindings:
            if self.parent:
                return self.parent.resolve(symbol)
            else:
                raise SchemeError("unknown identifier: ", symbol)
        else:
            return self.bindings[symbol]
        
    # END PROBLEM 2/3


##############
# Procedures #
##############

class Procedure:
    """The supertype of all Scheme procedures."""

def scheme_procedurep(x):
    return isinstance(x, Procedure)
  
class BuiltinProcedure(Procedure):
    """A Scheme procedure defined as a Python function."""

    def __init__(self, fn, use_env=False, name='builtin'):
        self.name = name
        self.fn = fn
        self.use_env = use_env

    def __str__(self):
        return '#[{0}]'.format(self.name)

    def apply(self, args, env):
        """Apply SELF to ARGS in ENV, where ARGS is a Scheme list.

        >>> env = create_global_frame()
        >>> plus = env.bindings['+']
        >>> twos = Pair(2, Pair(2, nil))
        >>> plus.apply(twos, env)
        4
        """
        # BEGIN PROBLEM 2
        argv = []
        while args != nil:
            argv.append(args.first)
            args = args.rest
        if self.use_env:
            argv.append(env)

        try:
            # print("DEBUG: builtin ", self.name, argv)
            ret = self.fn(*argv)
        except TypeError as e:
            print(f"DEBUG: {self.name}", e)
            raise SchemeError(f"incorrect number of arguments {self.name}")
        return ret
        # END PROBLEM 2

class LambdaProcedure(Procedure):
    """A procedure defined by a lambda expression or a define form."""

    def __init__(self, formals, body, env):
        """A procedure with formal parameter list FORMALS (a Scheme list),
        whose body is the Scheme list BODY, and whose parent environment
        starts with Frame ENV."""
        self.name = 'Lambda'
        if body == nil:
            raise SchemeError('lambda too few operands in form')

        self.formals = formals
        self.body = body
        self.env = env
        self.closure_frame = env

    # BEGIN PROBLEM 3
    "*** YOUR CODE HERE ***"
    def apply(self, args, __env__):
        """
        args:    a Pair whose element has already eval
        __env__: should not use in here
        """
        forms = self.formals
        print("DEBUG: Lambda", args)
        tmp_frame = Frame(self.closure_frame)
        while args != nil and forms != nil:
            tmp_frame.define(forms.first, args.first)
            args = args.rest
            forms = forms.rest

        p_body = self.body
        # tail recursion, left the last expression
        while p_body != nil and p_body.rest != nil:
            ret = scheme_eval(p_body.first, tmp_frame)
            p_body = p_body.rest
        return make_tail_expr(tmp_frame, p_body.first)

    # END PROBLEM 3
    def __str__(self):
        return str(Pair('lambda', Pair(self.formals, self.body)))

    def __repr__(self):
        return 'LambdaProcedure({0}, {1}, {2})'.format(
            repr(self.formals), repr(self.body), repr(self.env))


def add_builtins(frame, funcs_and_names):
    """Enter bindings in FUNCS_AND_NAMES into FRAME, an environment frame,
    as built-in procedures. Each item in FUNCS_AND_NAMES has the form
    (NAME, PYTHON-FUNCTION, INTERNAL-NAME)."""
    for name, fn, proc_name in funcs_and_names:
        frame.define(name, BuiltinProcedure(fn, name=proc_name))

#################
# Special Forms #
#################

"""
How you implement special forms is up to you. We recommend you encapsulate the
logic for each special form separately somehow, which you can do here.
"""

# BEGIN PROBLEM 2/3
"*** YOUR CODE HERE ***"
class SpecialForm(BuiltinProcedure):
    def apply(self, args, env):
        """ special form don't eval a expr, pass args to their func directly.
        args: original expression. the expression should not be eval
              valid args is the responsibility of self.fn.
              TODO: The mechanisms of special form and function are not completely unified.
        env: Current execution environment
        """
        print(f"DEBUG: SpecialForm {self.name} :")#, args)
        # try:
        if self.use_env:
            ret = self.fn(args, env)
        else:
            ret = self.fn(args)
        # except TypeError as e:
        #     print(f"DEBUG: {self.name}", e)
        #     raise SchemeError(f"{self.name} incorrect number of arguments {self.name}")

        return ret
# END PROBLEM 2/3

class SchemeMacro(SpecialForm):
    def __init__(self, formals, body):
        """A procedure with formal parameter list FORMALS (a Scheme list),
        whose body is the Scheme list BODY, and whose parent environment
        starts with Frame ENV."""
        self.name = 'SchemeMacro'

        p_forms = formals
        while p_forms != nil:
            if not isinstance(p_forms.first, str):
                raise SchemeError("define-macro: invalid formals")
            p_forms = p_forms.rest

        if body == nil:
            raise SchemeError('SchemeMacro too few operands in form')

        self.formals = formals
        self.body = body

    def apply(self, args, env):
        """
        args:    a Pair whose element has already eval
        __env__: should not use in here
        """
        forms = self.formals
        print("DEBUG: SchemeMacro", args)
        tmp_frame = Frame(env)
        while args != nil and forms != nil:
            tmp_frame.define(forms.first, args.first)
            args = args.rest
            forms = forms.rest
        print("DEBUG: SchemeMacro eval body", self.body.first)
        p_body = self.body

        while p_body != nil:
            ret = scheme_eval(p_body.first, tmp_frame)
            p_body = p_body.rest
        ret = scheme_eval(ret, env)
        return ret
# Utility methods for checking the structure of Scheme programs

def validate_form(expr, min, max=float('inf')):
    """Check EXPR is a proper list whose length is at least MIN and no more
    than MAX (default: no maximum). Raises a SchemeError if this is not the
    case.

    >>> validate_form(read_line('(a b)'), 2)
    """
    if not scheme_listp(expr):
        raise SchemeError('badly formed expression: ' + repl_str(expr))
    length = len(expr)
    if length < min:
        raise SchemeError('too few operands in form')
    elif length > max:
        raise SchemeError('too many operands in form')

def validate_formals(formals):
    """Check that FORMALS is a valid parameter list, a Scheme list of symbols
    in which each symbol is distinct. Raise a SchemeError if the list of
    formals is not a list of symbols or if any symbol is repeated.

    >>> validate_formals(read_line('(a b c)'))
    """
    symbols = set()
    def validate_and_add(symbol, is_last):
        if not scheme_symbolp(symbol):
            raise SchemeError('non-symbol: {0}'.format(symbol))
        if symbol in symbols:
            raise SchemeError('duplicate symbol: {0}'.format(symbol))
        symbols.add(symbol)

    while isinstance(formals, Pair):
        validate_and_add(formals.first, formals.rest is nil)
        formals = formals.rest

    # here for compatibility with DOTS_ARE_CONS
    if formals != nil:
        validate_and_add(formals, True)

def validate_procedure(procedure):
    """Check that PROCEDURE is a valid Scheme procedure."""
    if not scheme_procedurep(procedure):
        raise SchemeError('{0} is not callable: {1}'.format(
            type(procedure).__name__.lower(), repl_str(procedure)))

#################
# Dynamic Scope #
#################

class MuProcedure(Procedure):
    """A procedure defined by a mu expression, which has dynamic scope.
     _________________
    < Scheme is cool! >
     -----------------
            \   ^__^
             \  (oo)\_______
                (__)\       )\/\
                    ||----w |
                    ||     ||
    """
    # BEGIN NO PROMPT
    "*** YOUR CODE HERE ***"
    # END NO PROMPT

    def __init__(self, formals, body):
        """A procedure with formal parameter list FORMALS (a Scheme list) and
        Scheme list BODY as its definition."""
        if body == nil:
            raise SchemeError('Mu too few operands in form')
        self.name = 'Mu'
        self.formals = formals
        self.body = body

    # BEGIN PROBLEM EC
    "*** YOUR CODE HERE ***"
    def apply(self, args, env):
        """args is a Pair"""
        forms = self.formals;
        frame = Frame(env)
        print("DEBUG: Mu", args)
        while args != nil and forms != nil:
            frame.define(forms.first, scheme_eval(args.first, frame))
            args = args.rest
            forms = forms.rest
        if args != nil or forms != nil:
            raise SchemeError("lambda: Incorrect number of arguments to function call")

        p_body = self.body
        while p_body != nil:
            ret = scheme_eval(p_body.first, frame)
            p_body = p_body.rest
        return ret
    # END PROBLEM EC

    def __str__(self):
        return str(Pair('mu', Pair(self.formals, self.body)))

    def __repr__(self):
        return 'MuProcedure({0}, {1})'.format(
            repr(self.formals), repr(self.body))
# BEGIN PROBLEM EC
"*** YOUR CODE HERE ***"
# END PROBLEM EC


##################
# Tail Recursion #
##################


# Make classes/functions for creating tail recursive programs here?

def complete_apply(procedure, args, env):
    """Apply procedure to args in env; ensure the result is not an Unevaluated.
    Right now it just calls scheme_apply, but you will need to change this
    if you attempt the optional questions."""
    val = scheme_apply(procedure, args, env)
    # Add stuff here?
    return val

# BEGIN PROBLEM 8
"*** YOUR CODE HERE ***"
# END PROBLEM 8


####################
# Extra Procedures #
####################

def scheme_map(fn, s, env):
    validate_type(fn, scheme_procedurep, 0, 'map')
    validate_type(s, scheme_listp, 1, 'map')
    return s.map(lambda x: complete_apply(fn, Pair(x, nil), env))

def scheme_filter(fn, s, env):
    validate_type(fn, scheme_procedurep, 0, 'filter')
    validate_type(s, scheme_listp, 1, 'filter')
    head, current = nil, nil
    while s is not nil:
        item, s = s.first, s.rest
        if complete_apply(fn, Pair(item, nil), env):
            if head is nil:
                head = Pair(item, nil)
                current = head
            else:
                current.rest = Pair(item, nil)
                current = current.rest
    return head

def scheme_reduce(fn, s, env):
    validate_type(fn, scheme_procedurep, 0, 'reduce')
    validate_type(s, lambda x: x is not nil, 1, 'reduce')
    validate_type(s, scheme_listp, 1, 'reduce')
    value, s = s.first, s.rest
    while s is not nil:
        value = complete_apply(fn, scheme_list(value, s.first), env)
        s = s.rest
    return value

################
# Input/Output #
################

def read_eval_print_loop(next_line, env, interactive=False, quiet=False,
                         startup=False, load_files=()):
    """Read and evaluate input until an end of file or keyboard interrupt."""
    if startup:
        for filename in load_files:
            scheme_load(filename, True, env)
    while True:
        try:
            src = next_line()
            while src.more_on_line:
                expression = scheme_read(src)
                result = scheme_eval(expression, env)
                if not quiet and result is not None:
                    print(repl_str(result))
        except (SchemeError, SyntaxError, ValueError, RuntimeError) as err:
            if (isinstance(err, RuntimeError) and
                'maximum recursion depth exceeded' not in getattr(err, 'args')[0]):
                raise
            elif isinstance(err, RuntimeError):
                print('Error: maximum recursion depth exceeded')
            else:
                print('Error:', err)
        except KeyboardInterrupt:  # <Control>-C
            if not startup:
                raise
            print()
            print('KeyboardInterrupt')
            if not interactive:
                return
        except EOFError:  # <Control>-D, etc.
            print()
            return

def scheme_load(*args):
    """Load a Scheme source file. ARGS should be of the form (SYM, ENV) or
    (SYM, QUIET, ENV). The file named SYM is loaded into environment ENV,
    with verbosity determined by QUIET (default true)."""
    if not (2 <= len(args) <= 3):
        expressions = args[:-1]
        raise SchemeError('"load" given incorrect number of arguments: '
                          '{0}'.format(len(expressions)))
    sym = args[0]
    quiet = args[1] if len(args) > 2 else True
    env = args[-1]
    if (scheme_stringp(sym)):
        sym = eval(sym)
    validate_type(sym, scheme_symbolp, 0, 'load')
    with scheme_open(sym) as infile:
        lines = infile.readlines()
    args = (lines, None) if quiet else (lines,)
    def next_line():
        return buffer_lines(*args)

    read_eval_print_loop(next_line, env, quiet=quiet)

def scheme_open(filename):
    """If either FILENAME or FILENAME.scm is the name of a valid file,
    return a Python file opened to it. Otherwise, raise an error."""
    try:
        return open(filename)
    except IOError as exc:
        if filename.endswith('.scm'):
            raise SchemeError(str(exc))
    try:
        return open(filename + '.scm')
    except IOError as exc:
        raise SchemeError(str(exc))

def create_global_frame():
    """Initialize and return a single-frame environment with built-in names."""
    env = Frame(None)
    env.define('eval',
               BuiltinProcedure(scheme_eval, True, 'eval'))
    env.define('apply',
               BuiltinProcedure(complete_apply, True, 'apply'))
    env.define('load',
               BuiltinProcedure(scheme_load, True, 'load'))
    env.define('procedure?',
               BuiltinProcedure(scheme_procedurep, False, 'procedure?'))
    env.define('map',
               BuiltinProcedure(scheme_map, True, 'map'))
    env.define('filter',
               BuiltinProcedure(scheme_filter, True, 'filter'))
    env.define('reduce',
               BuiltinProcedure(scheme_reduce, True, 'reduce'))
    env.define('undefined', None)
    
    env.define('define', 
               SpecialForm(scheme_define, True, 'define'))

    env.define('quote', 
               SpecialForm(scheme_quote, False, 'quote'))
    env.define('begin', 
               SpecialForm(scheme_begin, True, 'begin'))
    env.define('lambda', 
               SpecialForm(scheme_lambda, True, 'lambda'))
    env.define("mu",
               SpecialForm(mu_lambda, True, 'mu'))
    env.define('and',
               SpecialForm(scheme_and, True, 'and'))
    env.define('or',
               SpecialForm(scheme_or, True, 'or'))
    env.define('not',
               SpecialForm(scheme_not, True, 'not'))
    env.define('if',
               SpecialForm(scheme_if, True, 'if'))
    env.define('cond',
               SpecialForm(scheme_cond, True, 'cond'))
    env.define('let',
               SpecialForm(scheme_let, True, 'let'))

    env.define('else', True)
    env.define('define-macro',
            SpecialForm(scheme_define_macro, True, 'define-macro'))
    add_builtins(env, BUILTINS)
    return env

@main
def run(*argv):
    import argparse
    parser = argparse.ArgumentParser(description='CS 61A Scheme Interpreter')
    parser.add_argument('--pillow-turtle', action='store_true',
                        help='run with pillow-based turtle. This is much faster for rendering but there is no GUI')
    parser.add_argument('--turtle-save-path', default=None,
                        help='save the image to this location when done')
    parser.add_argument('-load', '-i', action='store_true',
                       help='run file interactively')
    parser.add_argument('file', nargs='?',
                        type=argparse.FileType('r'), default=None,
                        help='Scheme file to run')
    args = parser.parse_args()

    import scheme
    scheme.TK_TURTLE = not args.pillow_turtle
    scheme.TURTLE_SAVE_PATH = args.turtle_save_path
    sys.path.insert(0, '')
    sys.path.append(os.path.dirname(os.path.abspath(os.path.dirname(scheme.__file__))))

    next_line = buffer_input
    interactive = True
    load_files = []

    if args.file is not None:
        if args.load:
            load_files.append(getattr(args.file, 'name'))
        else:
            lines = args.file.readlines()
            def next_line():
                return buffer_lines(lines)
            interactive = False

    read_eval_print_loop(next_line, create_global_frame(), startup=True,
                         interactive=interactive, load_files=load_files)
    tscheme_exitonclick()